package com.ideas.impl.mianshi;

/**
 * @Author lijian.wu
 * @Date 2024/4/17 21:32
 * 给定一个二叉搜索树，请找出其中第k小的元素
 *
 * 在二叉搜索树中查找第k小的元素，可以利用二叉搜索树的一个重要性质：二叉搜索树的中序遍历序列是有序的。
 * 因此，可以通过对二叉搜索树进行中序遍历并计数来找到第k小的元素。
 */
public class InOrderTraverse {

    private int count = 0; // 用于计数已遍历的节点
    private int result = Integer.MIN_VALUE; // 存储第k小的元素

    public int kthSmallest(TreeNode root, int k) {
        inOrderTraverse(root, k);
        return result;
    }

    private void inOrderTraverse(TreeNode node, int k) {
        if (node == null) return;
        inOrderTraverse(node.left, k);

        count++;
        if(count == k){
            System.out.println(result = node.val);
            // 找到第k小的元素后返回
            return;
        }

        inOrderTraverse(node.right, k);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}